package performance;

import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;
public class QuickSort_NoRec_Random {

	public static Random pivotRandom = new Random();
	static 
	{
		pivotRandom.setSeed(System.currentTimeMillis());
	}
	public static int selectPivot(int left, int right)
	{
//		return (left + right) / 2;
		int pivot = Math.abs(pivotRandom.nextInt()) % (right - left) + left;
		return pivot;
	}
	public static int partition(ArrayList<Double> des, int left, int right ,int pivot)
	{
		double temp = des.get(pivot);
		des.set(pivot, des.get(right));
//		des.set(right, temp);
		int i = left;
		int j = right;
		while( i != j)
		{
			while (des.get(i) < temp && i < j)
				i++;
			if (i < j)
			{
				des.set(j, des.get(i));
				j --;
			}
			while (des.get(j) > temp && i < j)
				j --;
			if (i < j)
			{
				des.set(i, des.get(j));
				i ++;
			}
		}
		des.set(i, temp);
		return i;
	}
	public static void qsort(ArrayList<Double> a, int left, int right)
	{
		Stack<BoardStruct> boardStack = new Stack<BoardStruct>();
		BoardStruct oneBoard = new BoardStruct(left, right);
		boardStack.add(oneBoard);
		
		while(! boardStack.isEmpty())
		{
			BoardStruct thisBoard = boardStack.pop();
			if (thisBoard.left >= thisBoard.right)
			{
				continue;
			}
			int pivot = selectPivot(thisBoard.left, thisBoard.right);
			pivot = partition(a, thisBoard.left, thisBoard.right, pivot);
			BoardStruct leftBoard = new BoardStruct(thisBoard.left, pivot - 1);
			boardStack.push(leftBoard);
			BoardStruct rightBoard = new BoardStruct( pivot + 1, thisBoard.right);
			boardStack.push(rightBoard);
		}
	}
	public static void main(String args[])
	{
		ArrayList<Double> a = new ArrayList<Double>();
//		a.add(0.1111);
//		a.add(0.01111);
//		a.add(0.001111);
//		a.add(0.1111);
//		a.add(0.1111);
//		a.add(0.1111);
//		a.add(0.0012);
//		a.add(0.1111);
//		a.add(0.11231211);
//		a.add(1.1111);
//		a.add(3.1111);
//		a.add(1.1111);
//		a.add(0.118231);
//		qsort(a, 0, a.size()-1);
		
		Random random = new Random();
		for (int i=0; i<1000000; i++)
		{
			a.add(random.nextDouble());
		//	a.add((double)i);
		}
		long start = System.currentTimeMillis();
		qsort(a, 0, a.size()-1);
		long end = System.currentTimeMillis();
		System.out.println("use time: " + (end - start));
		for (int i=0; i<a.size(); i++)
		{
//			System.out.println((i+1) + ": " +  a.get(i));
			if (i > 0)
			{
				if (a.get(i-1) > a.get(i))
				{
					System.out.println("Wrong");
					break;
				}
			}
		}
	}
	
}


